/**
  * Author: Mei
  * Date: 2020-12-17 11:29
  * Description: 在最大头结点之前插入x
  *
  */
#include<iostream>
#include <stack>

using namespace std;

struct Node {
    int data;
    struct Node *next;
};

void insert_node(struct Node *head, struct Node *x) {
    struct Node *p, *q, *max, *prev;
    prev = head; //最大值的前驱
    max = head->next; //最大结点
    p = max->next; //遍历的结点
    q = head->next; //每次遍历结点的前驱
    while (p != NULL) {
        if (p->data > max->data) { //找到最大结点和前驱结点
            prev = q;
            max = p;
        }
        q = p;
        p = p->next;
    }
    if (prev != NULL) { //将x插入
        x->next = prev->next;
        prev->next = x;
    }
}

class MinStack1 {
public:
    /** initialize your data structure here. */
    MinStack() {
        stack = new int[20];
        st_top = -1;
    }

    void push(int x) {
        ++st_top;
        stack[st_top] = x;
    }

    void pop() {
        if (st_top > 0) {
            --st_top;
        }
    }

    int top() {
        if (st_top >= 0) {
            return stack[st_top];
        }
        return -1;
    }

    int getMin() {
        int min = 0;
        if (st_top >= 0) {
            min = stack[0];
            for (int i = 1; i <= st_top; ++i) {  //要求在常量时间内获取最小值 这种方法不行
                if (stack[i] < min) {
                    min = stack[i];
                }
            }
        }
        return min;
    }

private:
    int *stack;
    int st_top;

};

class MinStack { //空间换时间
public:
    /** initialize your data structure here. */
    MinStack() {
        temp_stack.push(INT_MAX);
    }

    void push(int x) {
        data_stack.push(x);
        temp_stack.push(min(x, temp_stack.top()));
    }

    void pop() {
        data_stack.pop();
        temp_stack.pop();
    }

    int top() {
        return data_stack.top();
    }

    int getMin() {
        return temp_stack.top();
    }

private:
    stack<int> data_stack; //数据栈
    stack<int> temp_stack; //辅助栈
};

class MinStack2 {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack2() {
        min_stack.push(INT_MAX);
    }

    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }

    void pop() {
        x_stack.pop();
        min_stack.pop();
    }

    int top() {
        return x_stack.top();
    }

    int getMin() {
        return min_stack.top();
    }
};

int main() {
    MinStack *minStack = new MinStack();
    minStack->push(-2);
    minStack->push(0);
    minStack->push(-3);
    cout << minStack->getMin() << endl;
    minStack->pop();
    minStack->pop();
    cout << minStack->top() << endl;
    cout << minStack->getMin() << endl;


    return 0;
}
